#include "BTreeNode.h"

using namespace std;

// declare leaf node
BTLeafNode::BTLeafNode()
{
	memset(buffer, 0, PageFile::PAGE_SIZE);
}

// declare non leaf node
BTNonLeafNode::BTNonLeafNode() 
{
	memset(buffer, 0, PageFile::PAGE_SIZE);
}

/*
 * Read the content of the node from the page pid in the PageFile pf.
 * @param pid[IN] the PageId to read
 * @param pf[IN] PageFile to read from
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTLeafNode::read(PageId pid, const PageFile& pf)
{ 
	// read pid into buffer
	return pf.read(pid, buffer);
}
    
/*
 * Write the content of the node to the page pid in the PageFile pf.
 * @param pid[IN] the PageId to write to
 * @param pf[IN] PageFile to write to
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTLeafNode::write(PageId pid, PageFile& pf)
{ 
	// write pid from buffer
	return pf.write(pid, buffer); 
}

/*
 * Return the number of keys stored in the node.
 * @return the number of keys in the node
 */
int BTLeafNode::getKeyCount()
{ 
	// store size of buffer into count
	int count = 0;
	memcpy(&count, &buffer, sizeof(int));
	return count;
}

/*
 * Insert a (key, rid) pair to the node.
 * @param key[IN] the key to insert
 * @param rid[IN] the RecordId to insert
 * @return 0 if successful. Return an error code if the node is full.
 */
RC BTLeafNode::insert(int key, const RecordId& rid)
{ 
	// check node is not full
	if(getKeyCount() >= 80)
	{
		return RC_NODE_FULL;
	}
	
	// find the place to insert
	char* iterateBuffer = &(buffer[0]) + sizeof(int) + sizeof(PageId);
	int currentKey = 0;
	int i = 0;
	
	while (iterateBuffer) {
		memcpy(&currentKey, iterateBuffer, sizeof(int));
		if(currentKey == 0) {
			break;
		}
		if (currentKey < key) {
			iterateBuffer += (sizeof(RecordId) + sizeof(int));
			i++;
		} else {
			break;
		}
	}
	
	if (&(buffer[PageFile::PAGE_SIZE]) - iterateBuffer < 20) 
	{
		return RC_NODE_FULL;
	}
	
	// insert the new data into the buffer and shift the buffer data down
	char* temp = (char*)malloc(PageFile::PAGE_SIZE * sizeof(char));
	memset(temp, 0, PageFile::PAGE_SIZE);
	
	int size = getKeyCount() * (sizeof(RecordId) + sizeof(int));
	
	if(currentKey != 0 && size > 0) {
		memcpy(temp, iterateBuffer, size - ((sizeof(RecordId) + sizeof(int)) * i));
		memset(iterateBuffer, 0, size - ((sizeof(RecordId) + sizeof(int)) * i));
	}
	
	memcpy(iterateBuffer, &key, sizeof(int));
	iterateBuffer += sizeof(int);
	memcpy(iterateBuffer, &rid, sizeof(RecordId));
	
	iterateBuffer += sizeof(RecordId);
	if(currentKey != 0 && size > 0) {
		memcpy(iterateBuffer, temp, size - ((sizeof(RecordId) + sizeof(int)) * i));
	}
	
	free(temp);
	
	// update the new key count
	int keyCount = getKeyCount();
	keyCount++;
	memcpy(&(buffer[0]), &keyCount, sizeof(int));
	
	return 0;
}

/*
 * Insert the (key, rid) pair to the node
 * and split the node half and half with sibling.
 * The first key of the sibling node is returned in siblingKey.
 * @param key[IN] the key to insert.
 * @param rid[IN] the RecordId to insert.
 * @param sibling[IN] the sibling node to split with. This node MUST be EMPTY when this function is called.
 * @param siblingKey[OUT] the first key in the sibling node after split.
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTLeafNode::insertAndSplit(int key, const RecordId& rid, BTLeafNode& sibling, int& siblingKey)
{ 
	// Check that node is full before splitting
  	/*if (getKeyCount() < 80)
  	{
    	return RC_INVALID_FILE_FORMAT;
  	}*/
  	
  	char* iterateBuffer = &(buffer[0]) + sizeof(int) + sizeof(PageId);
	int i = 0;
	
	while(i < (getKeyCount() / 2)) 
	{
		iterateBuffer += (sizeof(RecordId) + sizeof(int));
		i++;
	}
	
	char* temp = (char*) malloc(1024 * sizeof(char));
	char* free_Temp = temp;
		
	// copy bottom half of data into temp
	int size = getKeyCount() * (sizeof(RecordId) + sizeof(int));
	memset(temp, 0, PageFile::PAGE_SIZE * sizeof(char));
	memcpy(temp, iterateBuffer, size - ((sizeof(RecordId) + sizeof(int)) * (getKeyCount() / 2)));
	
	// delete data from node
	memset(iterateBuffer, 0, size - ((sizeof(RecordId) + sizeof(int)) * (getKeyCount() / 2)));
	int newKeyCount = getKeyCount() / 2;
	memcpy(buffer, &newKeyCount, sizeof(int));
	
	// insert data from orig. node and insert into new node
	while(temp) {
		int j = 0;
		RecordId id;
		
		memcpy(&j, temp, sizeof(int));
		
		if(j == 0) 
		{
			break;
		}
		
		temp += sizeof(int);
		memcpy(&id, temp, sizeof(RecordId));
		temp += sizeof(RecordId);

		if(sibling.insert(j, id) != 0) 
		{
			free(free_Temp);
			return RC_FILE_WRITE_FAILED;
		}
	}
	
	free(free_Temp);

	RecordId id;
	sibling.readEntry(0, siblingKey, id);
	
	if(key >= siblingKey) 
	{
		if(sibling.insert(key, rid) != 0) 
		{
			return RC_FILE_WRITE_FAILED;
		}
	} 
	else 
	{
		if(insert(key, rid) != 0) 
		{
			return RC_FILE_WRITE_FAILED;
		}
	}
	
	sibling.readEntry(0, siblingKey, id);
	  	
	return 0; 
}

/*
 * Find the entry whose key value is larger than or equal to searchKey
 * and output the eid (entry number) whose key value >= searchKey.
 * Remeber that all keys inside a B+tree node should be kept sorted.
 * @param searchKey[IN] the key to search for
 * @param eid[OUT] the entry number that contains a key larger than or equalty to searchKey
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTLeafNode::locate(int searchKey, int& eid)
{
	char* iterateBuffer = &(buffer[0]) + sizeof(int);
	int currentKey = 0;
	int i = 0;

	while(iterateBuffer)
	{
		// get the current key from the buffer
		memcpy(&currentKey, iterateBuffer, sizeof(int));
		
		// if there's no key
		if(currentKey == 0 || currentKey >= searchKey)
		{
			eid = i;
			break;
		}
		iterateBuffer += (sizeof(RecordId) + sizeof(int));
		i++;
	}
	
	return 0; 
}

/*
 * Read the (key, rid) pair from the eid entry.
 * @param eid[IN] the entry number to read the (key, rid) pair from
 * @param key[OUT] the key from the entry
 * @param rid[OUT] the RecordId from the entry
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTLeafNode::readEntry(int eid, int& key, RecordId& rid)
{ 
  	char* iterateBuffer = &(buffer[0]) + sizeof(int) + sizeof(PageId);
	int i = 0;
	
	// go to eid in buffer
	while(i < eid && iterateBuffer)
	{
		iterateBuffer += (sizeof(RecordId) + sizeof(int));
		i++;
	}
	
	memcpy(&key, iterateBuffer, sizeof(int));
	iterateBuffer += sizeof(int);
	memcpy(&rid, iterateBuffer, sizeof(RecordId));
	
	return 0; 
}

/*
 * Return the pid of the next slibling node.
 * @return the PageId of the next sibling node 
 */
PageId BTLeafNode::getNextNodePtr()
{ 
	char* iterateBuffer = &(buffer[0]) + sizeof(int);
	PageId pid;
	
	// get next pid fro pagefile
	memcpy(&pid, iterateBuffer, sizeof(PageId));
	// pid = null if no next node
	return pid;
}

/*
 * Set the pid of the next slibling node.
 * @param pid[IN] the PageId of the next sibling node 
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTLeafNode::setNextNodePtr(PageId pid)
{ 
	char* iterateBuffer = &(buffer[0]) + sizeof(int);
	
	memcpy(iterateBuffer, &pid, sizeof(PageId));

	return 0;
}
 
 
 
/***************************************************
				non leaf node
***************************************************/

/*
 * Read the content of the node from the page pid in the PageFile pf.
 * @param pid[IN] the PageId to read
 * @param pf[IN] PageFile to read from
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTNonLeafNode::read(PageId pid, const PageFile& pf)
{ 
	return pf.read(pid, buffer); 
}
    
/*
 * Write the content of the node to the page pid in the PageFile pf.
 * @param pid[IN] the PageId to write to
 * @param pf[IN] PageFile to write to
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTNonLeafNode::write(PageId pid, PageFile& pf)
{ 
	return pf.write(pid, buffer);
}

/*
 * Return the number of keys stored in the node.
 * @return the number of keys in the node
 */
int BTNonLeafNode::getKeyCount()
{ 
	// store size of buffer into count
	int count = 0;
	memcpy(&count, &buffer, sizeof(int));
	return count;
}

/*
 * Insert a (key, pid) pair to the node.
 * @param key[IN] the key to insert
 * @param pid[IN] the PageId to insert
 * @return 0 if successful. Return an error code if the node is full.
 */
RC BTNonLeafNode::insert(int key, PageId pid)
{ 
	int size = getKeyCount() * (sizeof(RecordId) + sizeof(int));
	if(size >= PageFile::PAGE_SIZE - (sizeof(RecordId) + sizeof(int)))
	{
		return RC_NODE_FULL;
	}
	
  	char* iterateBuffer = &(buffer[0]) + sizeof(int) + sizeof(PageId);
	int currentKey = 0;
	int eid = 0;
	
	find(key, eid, iterateBuffer, currentKey);
	
	if(currentKey == key)
	{
		iterateBuffer += sizeof(int);
		memcpy(iterateBuffer, &pid, sizeof(PageId));
		return 0;
	}
	if (iterateBuffer == &(buffer[PageFile::PAGE_SIZE]))
	{
		return RC_FILE_WRITE_FAILED;
	}
	
	char* temp = (char*) malloc(PageFile::PAGE_SIZE * sizeof(char));
	memset(temp, 0, PageFile::PAGE_SIZE);
	
	if(currentKey != 0 && size > 0) 
	{
		memcpy(temp, iterateBuffer, size - ((sizeof(RecordId) + sizeof(int)) * eid));
		memset(iterateBuffer, 0, size - ((sizeof(RecordId) + sizeof(int)) * eid));
	}
	
	memcpy(iterateBuffer, &key, sizeof(int));
	iterateBuffer += sizeof(int);
	memcpy(iterateBuffer, &pid, sizeof(PageId));
	iterateBuffer += sizeof(PageId);
	
	if(currentKey != 0 && size > 0) 
	{
		memcpy(iterateBuffer, temp, size - ((sizeof(RecordId) + sizeof(int)) * eid));
	}
	
	free(temp);
		
	int keyCount = getKeyCount();
	keyCount++;
	memcpy(&(buffer[0]), &keyCount, sizeof(int));
	
	return 0;
}

RC BTNonLeafNode::find(int searchKey, int& eid, char* &iterateBuffer, int& currentKey)
{ 
	while(iterateBuffer)
	{
		// get the current key from the buffer
		memcpy(&currentKey, iterateBuffer, sizeof(int));
		
		// if there's no key
		if(currentKey == 0)
		{
			break;
		}
		// first entry who's key is larger or equal to search key
		if(currentKey >= searchKey)
		{
			break;
		}
		// keep going until above statement is tree
		else
		{
			iterateBuffer += sizeof(RecordId) + sizeof(int);
			eid++;
		}
	}
	
	return 0; 
}

/*
 * Insert the (key, pid) pair to the node
 * and split the node half and half with sibling.
 * The middle key after the split is returned in midKey.
 * @param key[IN] the key to insert
 * @param pid[IN] the PageId to insert
 * @param sibling[IN] the sibling node to split with. This node MUST be empty when this function is called.
 * @param midKey[OUT] the key in the middle after the split. This key should be inserted to the parent node.
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTNonLeafNode::insertAndSplit(int key, PageId pid, BTNonLeafNode& sibling, int& midKey)
{ 
	char* iterateBuffer = &(buffer[0]) + sizeof(int);
	int i = 0;
	
	while(i < (getKeyCount() / 2)) 
	{
		iterateBuffer += (sizeof(RecordId) + sizeof(int));
		i++;
	}
	
	char* temp = (char*) malloc(PageFile::PAGE_SIZE * sizeof(char));
	char* free_Temp = temp;
		
	// copy bottom half of data into temp
	int size = getKeyCount() * (sizeof(RecordId) + sizeof(int));
	memset(temp, 0, PageFile::PAGE_SIZE * sizeof(char));
	memcpy(temp, iterateBuffer, size - ((sizeof(RecordId) + sizeof(int)) * (getKeyCount() / 2)));
	
	// delete data from node
	memset(iterateBuffer, 0, size - ((sizeof(RecordId) + sizeof(int)) * (getKeyCount() / 2)));
	int newKeyCount = getKeyCount() / 2;
	memcpy(buffer, &newKeyCount, sizeof(int));
	
	// insert data from orig. node and insert into new node
	while(temp) {
		int j = 0;
		PageId id;
		
		memcpy(&j, temp, sizeof(int));
		
		if(j == 0) 
		{
			break;
		}
		
		temp += sizeof(int);
		memcpy(&id, temp, sizeof(RecordId));
		temp += sizeof(RecordId);

		if(sibling.insert(j, id) != 0) 
		{
			free(free_Temp);
			return RC_FILE_WRITE_FAILED;
		}
	}
	
	free(free_Temp);
	
	char* iterateBuffer2 = &(buffer[0]) + sizeof(int);
	
	iterateBuffer2 += sizeof(PageId);
		
	memcpy(&midKey, iterateBuffer2, sizeof(int));
	
	
	if(key < midKey) 
	{
		if( insert(key, pid) != 0 )
		{
			return RC_FILE_WRITE_FAILED;
		}
	} 
	else
	{
		if( sibling.insert(key, pid) != 0 )
		{
			return RC_FILE_WRITE_FAILED;
		}
	}
	
	return 0; 
}

/*
 * Given the searchKey, find the child-node pointer to follow and
 * output it in pid.
 * @param searchKey[IN] the searchKey that is being looked up.
 * @param pid[OUT] the pointer to the child node to follow.
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTNonLeafNode::locateChildPtr(int searchKey, PageId& pid)
{
	char* iterateBuffer = &(buffer[0]) + (2 * sizeof(int));
	int currentKey = 0;
	
	while(iterateBuffer)
	{
		memcpy(&currentKey, iterateBuffer, sizeof(int));
		if(currentKey != 0 && currentKey < searchKey)
		{
			iterateBuffer += sizeof(int);
		}
		else
		{
			iterateBuffer -= sizeof(PageId);
			memcpy(&pid, iterateBuffer, sizeof(PageId));
			break;
		}
		iterateBuffer += (sizeof(PageId) + sizeof(int));
	}
	
	return 0;
}

/*
 * Initialize the root node with (pid1, key, pid2).
 * @param pid1[IN] the first PageId to insert
 * @param key[IN] the key that should be inserted between the two PageIds
 * @param pid2[IN] the PageId to insert behind the key
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTNonLeafNode::initializeRoot(PageId pid1, int key, PageId pid2)
{ 
	char* iterateBuffer = &(buffer[0]) + sizeof(int);
	
	memcpy(iterateBuffer, &pid1, sizeof(PageId));
	iterateBuffer += sizeof(PageId);
	
	memcpy(iterateBuffer, &key, sizeof(int));
	iterateBuffer += sizeof(int);
	
	memcpy(iterateBuffer, &pid2, sizeof(PageId));

	int i = 1;
	memcpy(buffer, &i, sizeof(int));

	return 0;
}
